package com.lwl.Algorithmic_data_structure.class17经典递归;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author lwl
 * @Description 逆序一个栈 不使用额外空间，及使用递归
 * @date 2023/6/2 20:27
 */
public class Code05reverseStackRecursive {

    public static void main(String[] args) {
        LinkedList<Integer> stack = new LinkedList<>(Arrays.asList(1, 2, 3));
        for (Integer element : stack) {
            System.out.println(element);
        }
        reverseStackRecursive(stack);
        System.out.println("==========");
        for (Integer element : stack) {
            System.out.println(element);
        }
    }

    static public void reverseStackRecursive(LinkedList<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        // 获取最后一个元素
        int tail = pushStackTail(stack);
        // 逆序
        reverseStackRecursive(stack);
        stack.push(tail);
    }

    static public int pushStackTail(LinkedList<Integer> stack) {
        Integer res = stack.removeFirst();
        if (stack.isEmpty()) {
            return res;
        }
        int last = pushStackTail(stack);
        stack.push(res);
        return last;
    }

}
